Міністерство освіти і науки України
Національний університет „Львівська Політехніка”
Кафедра електронних
обчислювальних машин
Курсова робота
„Структури даних та алгоритми”
Завдання 1. Представлення даних в пам’яті комп’ютера.
Дослідити представлення в пам’яті комп’ютера даних статичної структури. Розглянути основні прості (цілі, дійсні, символьні, логічні) і складові або фундаментальні (масиви, записи, рядки символів) структури даних.
const zz1 = місяць народження (дві цифри);
zz2 = дві останні цифри року народження; *
zz3 = zz2-30;
var b1 : Boolean;
b2 : Wordbool;
b3 : Longbool;
ch : Char;
i1 : Byte;
i2 : Shortint;
i3 : Word;
i4 : Integer;
i5 : Longint;
r1 : Real;
r2 : Single;
r3 : Double;
r4 : Extended;
r5 : Comp;
str : String [15];
p : (Прізвище, Ім’я, По-батькові); **
d : zz1 .. zz2;
m : array [1..2, 1..5] of char;
rec : record
a1, a2 : string[15];
b1, b2, b3 : char;
c1, c2 : integer
end;
s : set of zz1 .. zz3 ;
f : text;
* - Замість місяця і року народження підставляти свої конкретні дати (по дві цифри кожна).
** - Замість Прізвище, Ім’я, По-батькові підставляти свої конкретні значення, записані латинськими літерами ( перша літера - велика, решта – малі) .
Тестування провести для наступних значень змінних:
true, якщо день народження парне число;
b1 =
false, якщо день народження непарне число;
b2 := succ(b1);
b3 := pred(pred(b1));
ch – перша літера Прізвища (велика українська літера);
i1 – день народження;
i2 := -i1;
i3 := i1*125;
i4 := -i3;
i5 := -i3;
r1– дробове число: ціла частина – місяць, а дробова – рік народження;
r2 := r1*125;
r3 := -r2;
r4 := r2;
r5 := i5;
str – Прізвище ( українські літери, перша - велика, решта - малі);
p – Ім’я ( латинські літери, перша - велика, решта - малі);
d – число, яке відповідає дню народження + 15;
m[1,1] – символ, який відповідає першій цифрі номера домашнього телефону;
m[1,2] – символ, який відповідає другій цифрі;
m[1,3] := ’0’;
m[1,4] – символ, який відповідає третій цифрі;
m[1,5] := ’0’;
m[2,1] := ’0’;
m[2,2] - символ, який відповідає четвертій цифрі;
m[2,3] := ’0’;
m[2,4] - символ, який відповідає п’ятій цифрі;
m[2,5] - символ, який відповідає шостій цифрі;
{Якщо домашнього телефону немає, обрахунки проводити для кафедрального телефону, його номер 398196: m[1,1]:=’3’; m[1,2]:=’9’; m[1,4]:=’8’; m[2,2]:=’1’; m[2,4]:=’9’; m[2,5]:=’6’;}
rec.a1 – назва міста в адресі прописки ( українські літери, перша - велика, решта - малі);
rec.a2 – назва вулиці в адресі прописки ( українські літери, перша - велика, решта - малі);
rec.с1 – номер будинку в адресі прописки;
rec.с2 – номер квартири в адресі прописки;
rec.b1 := ’,’ ;
rec.b2 := ’,’ ;
rec.b3 := ’/’ ;
S – множина всіх чисел кратних k з діапазону zz1 .. zz3,
( k = № mod 5 + 2 , де № - порядковий номер студента в журналі викладача ).
Завдання 2. Сортування і пошук.
Реалізувати вказаний нижче метод сортування і пошуку в послідовності, представленій у вигляді масиву чисел або у вигляді лінійного однозв’язаного списку, елементи якого містять по декілька інформаційних полів (в загальному випадку – великих об’єми інформації), одне з яких є ключовим, і всі зміни положення елементів в послідовності виконуються не перестановкою самих елементів, а перестановкою їх зв’язків. Намалювати схему алгоритму для конкретного прикладу послідовності з десяти цілих чисел зі знаком. Дослідити метод на стійкість. Дослідити ефективність метода. Для цього визначити середні значення кількості порівнянь, кількості перестановок і часу виконання. Порівняти отримані характеристики з аналогічними даними для основних простих методів сортування (вставки, вибору, обміну), зробити висновки про ефективність метода, що досліджується. Дослідити метод на економність використання пам’яті. Дослідити метод на можливу специфіку вхідної послідовності (чи може послідовність містити елементи з однаковими ключа...
